#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
//#include<string>
using namespace std;
class Solution {
public:
    static vector<vector<string>> creatPad()
    {
        vector<vector<string>> numPad;
        numPad.push_back({ "" });
        numPad.push_back({ "" });
        numPad.push_back({ "a","b","c" });
        numPad.push_back({ "d","e","f" });
        numPad.push_back({ "g","h","i" });
        numPad.push_back({ "j","k","l" });
        numPad.push_back({ "m","n","o" });
        numPad.push_back({ "p","q","r","s" });
        numPad.push_back({ "t","u","v" });
        numPad.push_back({ "w","x","y","z" });
        return numPad;
    }
    static void solve(string digits, vector<string>& answer, const vector<vector<string>>& numPad)
    {
        //end
        if (digits.size() == 0)
        {
            answer.push_back("");
            return;
        }
        //continue
        int flg = digits[0] - '0';
        digits.erase(digits.begin());

        vector<string> Ans;
        solve(digits, Ans, numPad);
        for (auto numPadAnswer : numPad[flg])
        {
            for (auto AnsAnswer : Ans)
            {
                answer.push_back(numPadAnswer + AnsAnswer);
            }
        }
    }
    static vector<string> letterCombinations(string digits)
    {
        vector<string> answer;
        if (digits.size() == 0)
            return answer;
        vector<vector<string>> numPad = creatPad();
        solve(digits, answer, numPad);
        return answer;
    }
};

int main()
{
    vector<string> v = { string("aa"),string("bb"),string("cc")};
    for (auto ch : v)
        cout << ch << ' ';
    return 0;
}